/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yinsh
 * Date: 2025-02-21
 * Time: 11:05
 */
public class Test {
    public void qSort (int[] array) {
        qSortFunc (array,0,array.length-1);
    }

    private void qSortFunc (int[] array,int left,int right) {
        if (left >= right) return;
        int pivot = partition (array,left,right);
        while (left < right) {
            qSortFunc(array,left,pivot);
            left = pivot + 1;
            pivot = right;
        }
    }


    private int partition (int[] array,int left,int right) {
        int key = array[left];
        int prev = left;
        int cur = left+1;
        while (cur < array.length) {
            while (array[cur] < key && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

    private void swap (int[] array,int x,int y) {
        int tamp = array[x];
        array[x] = array[y];
        array[y] = tamp;
    }
}
